package com.cande.loki.exercise.algorithm;

/**
 * @BelongsProject: loki
 * @BelongsPackage: com.cande.loki.exercise.algorithm
 * @Author: WANGAOFEI
 * @CreateTime: 2023-10-16  16:46
 * @Description: 判断单向链表是否成环,并找到环的入口
 * @Version: 1.0
 */
public class IsCycleListNode {
    public static void main(String[] args) {

    }




    public ListNode isCycle(ListNode head){
        if (head == null || head.next == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast!=null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow){ //快慢指针相遇  相遇之后从头节点出发和相遇节点出发 再次遇到就是环的入口
                ListNode newHead = head;
                while (newHead != slow){
                    newHead = newHead.next;
                    slow = slow.next;
                }
                return newHead;
            }
        }
        return null;
    }
}
